package com.lw.leetcode.dp.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 805. 数组的均值分割
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/14 9:32
 */
public class SplitArraySameAverage {

    public static void main(String[] args) {
        SplitArraySameAverage test = new SplitArraySameAverage();

        // true   [1,4,5,8] 和 [2,3,6,7]
//        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};

        // true   [60, 59, 61] 和 [30, 90, 10, 110]
//        int[] arr = {60, 59, 61, 30, 90, 10, 110};

        // true
//        int[] arr = {1, 1, 1, 1, 1, 1, 1};

        // true [5, 11] 和 [3, 19, 2]
//        int[] arr = {5, 3, 11, 19, 2};

        // true  [0, 8] 和 [0,3,9]
//        int[] arr = {0, 0, 3, 9, 8};

        // false
//        int[] arr = {60, 59, 61, 30, 90, 10, 111};

        // false
        int[] arr = {3, 1};

        boolean b = test.splitArraySameAverage(arr);
        System.out.println(b);

    }

    public boolean splitArraySameAverage(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum == 0) {
            return true;
        }
        int[][] arr = new int[length][sum + 1];
        int t = sum;
        for (int i = 0; i < length - 1; i++) {
            if (t % length == 0 && find(nums, t / length, i, arr)) {
                return true;
            }
            t += sum;
        }
        return false;
    }

    private boolean find(int[] nums, int t, int n, int[][] arr) {
        int length = nums.length;
        int[] ints = arr[0];
        Arrays.fill(ints, 0);
        ints[nums[0]] = 1;
        for (int i = 1; i < length; i++) {
            int num = nums[i];
            ints = arr[i];
            int[] last = arr[i - 1];
            Arrays.fill(ints, 0);
            for (int j = 0; j <= t; j++) {
                int v = j - num;
                if (v == 0) {
                    ints[j] = (last[0] << 1) + 1;
                } else if (v > 0) {
                    ints[j] = last[v] << 1;
                }
                ints[j] |= last[j];
            }
        }
        int k = 1 << n;
        return (arr[length - 1][t] & k) == k;
    }

}
